The present invention relates to an arithmetic method and apparatus and a crypto processing apparatus and, more particularly, to an arithmetic method and apparatus and a crypto processing apparatus which are suitably used for crypto coprocessors and the like implemented in, for example, IC cards and information electric home appliances.
In implementing an LSI for public-key cryptography, a cryptosystem for performing an integer based operation of the RSA (Rivest-Shamir-Adleman) system or the like have been mainly used. In this system, an operation must be performed for an integer with a large number of digits. For this reason, if this system is applied to an IC card or the like, a special-purpose processor is required. Many systems that implement such special-purpose coprocessors to realize long integer based operations for crypto processing have already been put into practice.
Recently, attention has been given to cryptosystems based on an algebraic system called a finite field GF(2^m): Galois Field, especially elliptic curve cryptosystems of a finite field GF(2^m), instead of integer based cryptosystems.
In this cryptosystem using a finite field GF(2^m) arithmetic operation, the number of bits to be handled must be set to be as large as 160 or more as in an integer based operation system such as RSA. For this reason, if such a system is implemented on a device in which the performance of a CPU is low, e.g., an IC card, a relatively long processing time is required. Therefore, there are demands for an increase in the performance by using special-purpose hardware (coprocessors).
As described above, according to RSA as well as elliptic curve cryptography, special-purpose coprocessors must be prepared to realize high-speed crypto processing in IC cards and the like.
FIG. 23 shows the layout of an IC card LSI including a coprocessor for crypto processing. Referring to FIG. 23, in this LSI, a CPU, RAM, ROM, and EEPROM are integrated into one chip, and the coprocessor is comprised of a RAM, arithmetic section, and control section. The coprocessor assists the CPU in performing basic arithmetic operations for a public-key cryptography, e.g., a long exponentiation and the four fundamental operations of arithmetic under the control of the CPU.
FIG. 24 shows a coprocessor in the LSI shown in FIG. 23. In RSA, this component is implemented as an integer based multiplier for performing integer based operations.
In assembling an LSI of an elliptic curve cryptography, although the overall arrangement becomes identical or similar to that of the LSI shown in FIG. 23, a coprocessor for performing finite field GF(2^m) arithmetic operations must be prepared instead of a coprocessor for performing integer based operations.
FIG. 25 is a block diagram showing the hardware arrangement of a coprocessor for performing finite field GF(2^m) arithmetic operations with a polynomial base.
FIG. 25 shows a kind of arithmetic apparatus for a finite field GF(2^m) called a cyclotomic field using the special irreducible polynomial disclosed in “Hardware Implementation of Elliptic Curve Cryptosystem”, SCIS' 98-10. 1. C. This arithmetic apparatus has an arrangement capable of executing addition, square, multiply, and inverse operations on a finite field GF(2^m). With this arrangement, a finite field GF(2^m) arithmetic operation required to compute a point on an elliptic curve is executed. By integrating such an arithmetic apparatus into an IC, a coprocessor for finite field GF(2^m) arithmetic operations which can be applied to the LSI in FIG. 23 can be obtained.
In this case, each of adder and multiplier circuits is constituted by m EX-ORs, and a multiplier circuit 81 is implemented by the circuit arrangement shown in FIG. 26.
FIG. 26 shows a finite field GF(2^m) based multiplier circuit called a cyclotomic field.
The multiplier circuit 81 has m-bit input registers A and B. The multiplier circuit 81 inputs the coefficients of a polynomial a(x) as fixed values to the input register A and computes while shifting the coefficients of a polynomial b(x) from the most significant bit in response to respective clocks. Referring to FIG. 26, reference symbols D denote flip-flops constituting a feedback register. When m shifts are made, the values of the respective blocks D are loaded into an output register C, thus obtaining a(x)*b(x) as an operation result.
As is obvious from the comparison between the circuits shown in FIGS. 24 and 26, an integer based multiply operation and finite field GF(2^m) arithmetic operation of a polynomial base totally differ in their architectures for executing multiply operations. Attempts have therefore been made to form different hardware arrangements for the respective cryptosystems.
For a finite field GF(2^m) based modular multiplication in a fundamental operation for an elliptic curve cryptosystem, an arithmetic apparatus using a linear feedback shift register (LFSR) as a divide circuit using a polynomial f(x) on a finite of field GF(qm) is widely used. The modulo polynomial f(x) is:f(x)=fmxm+fm-1xm−1+ . . . +f1x+f0,fm=1
FIG. 27 is a block diagram showing the arrangement of a linear feedback shift register LFSR. In this LFSR 90, EX-OR adders 911 to 91m and 1-clock delay elements (to be referred to as registers hereinafter) 921 to 92m are alternately cascaded from the input side. In this arrangement, the output extracted from the mth register 92m is separately fed back to the m adders 911 to 91m through coefficient units 931 to 93m.
This LFSR 90 operates on a unit time (clock) basis. In the shift register, advancing an operation clock pulse by one clock is referred to as making a shift, and a number m of registers 921 to 92m incorporated in the shift register is referred to as the number of stages of the shift register.
When q=2, a 1-bit flip-flop can be applied to each of the registers 921 to 92m. Each of the coefficient units 931 to 93m multiplies “1” or “0”. When 1 is multiplied, a corresponding coefficient unit is connected, whereas when 0 is multiplied, a corresponding coefficient unit is not connected. As each of the adders 911 to 91m, a 2-input EX-OR is used.
In this LFSR 90, as the coefficients of a dividend polynomial are sequentially input from the input side (left side) from the higher orders, the coefficients of a quotient polynomial are sequentially output from the output side (right side) from higher orders. In this case, the contents of the respective registers (flip-flops) 921 to 92m upon completion of input of the 0th-order term of the dividend polynomial are the coefficients of a remainder polynomial.
In the arithmetic apparatus using the above LFSR 90, however, the registers 921 to 92m equal in number to the bits of a degree m are required, and hence the arrangement of the registers 921 to 92m is limited by the degree m. If, therefore, the degree m increases, the LFSR must be modified for each arithmetic apparatus.
Although attention is currently given to elliptic curve cryptosystems, RSA cryptosystems are still in the mainstream. It is therefore strongly required that even IC cards using elliptic curve cryptosystems comply with RAS cryptosystems.
When both a conventional integer based cryptosystem and a finite field GF(2^m) based cryptosystem are to be incorporated in the same IC card, coprocessors corresponding to the respective cryptosystems must be incorporated in the IC card according to the conventional techniques. If, however, two coprocessors are incorporated in the IC card, the chip area of the IC card, which is severely limited in terms of area, is undesirably reduced.
In a finite field GF(2^m) based modular multiplication, as the degree m increases, the LFSR must be modified for each arithmetic apparatus, thus imposing limitations in terms of hardware.